package com.veal98.tree;

import com.veal98.bean.TreeNode;

public class ConstructBinaryTreeFromPreorderAndInorderTraversal_105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 左闭右开
        return buildTree1(preorder, 0, preorder.length,
                          inorder, 0, inorder.length);
    }

    /**
     * @param preorder (左闭右开)
     * @param preLeft preorder 数组的起始下标
     * @param preRight preorder 数组的终止下标
     * @param inorder (左闭右开)
     * @param inLeft inorder 数组的起始下标
     * @param inRight inorder 数组的终止下标
     * @return
     */
    private TreeNode buildTree1(int[] preorder, int preLeft, int preRight,
                                int[] inorder, int inLeft, int inRight) {
        // 没有元素了
        if (inRight - inLeft < 1) {
            return null;
        }
        // 只有一个元素了
        if (inRight - inLeft == 1) {
            return new TreeNode(inorder[inLeft]);
        }

        // 前序数组的第一个节点为根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        // 在中序数组中找到根节点的位置
        int index = inLeft;
        for (; index < inRight; index ++) {
            if (inorder[index] == root.val) {
                break;
            }
        }

        // 构建左子树
        root.left = buildTree1(preorder, preLeft + 1, preLeft + (index - inLeft),
                               inorder, inLeft, index);
        // 构建右子树
        root.right = buildTree1(preorder, preLeft + (index - inLeft) + 1, preRight,
                                inorder, index + 1, inRight);

        return root;
    }
}
